#include <limits.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdio.h>

// Kruskal(克鲁斯卡尔)最小生成树算法

/**
 * @brief 最小生成树
 * 
 *  1. 树的要求：
 *      - 无环
 *      - 树链接到所有顶点
 *      - N个顶点则有N-1条边
 * 
 *  2. 最小生成树
 *      - 加权sum最小
 * 
 */

// 算法教程： https://www.bilibili.com/video/BV1Eb41177d1/?spm_id_from=333.337.search-card.all.click
typedef std::pair<int, int> pii;                // (节点, 权重)
typedef std::vector<std::vector<pii>> AdjList;  // AdjList邻接表;
typedef std::vector<std::vector<int>> Matrix;

AdjList edges = {{{1,4}, {7,8}},              // node0
                {{2,8}, {7,11}},              // node1
                {{1,8},{3,7},{8,2}},          // node2
                {{2,7},{4,9},{5,14}},         // node3
                {{3,9},{5,10}},               // node4
                {{6,2},{2,4},{3,14},{4,10}},  // node5
                {{7,1},{8,6},{5,2}},          // node6
                {{0,8},{1,11},{8,7},{6,1}},   // node7
                {{2,2},{7,7},{6,6}},          // node8
                };

struct Edge {
    int u, v, weight;
    Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {}
};

bool compareEdges(const Edge& e1, const Edge& e2) {
    return e1.weight < e2.weight;
}

int find(int u, std::vector<int>& parent) {
    while (u != parent[u])
        u = parent[u];
    return u;
}

void merge(int u, int v, std::vector<int>& parent,
        std::vector<int>& rank) {
    int pu = find(u, parent);
    int pv = find(v, parent);
    if (pu == pv) return;
    if (rank[pu] > rank[pv])
        parent[pv] = pu;
    else if (rank[pu] < rank[pv])
        parent[pu] = pv;
    else {
        parent[pu] = pv;
        rank[pv]++;
    }
}

/**
 * @brief  kruskal算法思路和步骤
 * 
 * @step   
 *   1. 将图中所有的边取出，按边长从小到大排列;
 *   2. 按照边长从小到大逐渐往图中回填，每回填一条边之间要判断如果回填该边图中是否存在环(如果成环则丢弃，否则即加入);
 *   3. 直到一斤选择了N-1条边;
 * 
 * @return void
 */
void kruskal(const AdjList& edges, Matrix& minSpanTree) {
    int numNodes = edges.size();
    std::vector<Edge> allEdges;

    // Convert adjacency list to vector of edges
    for (int u = 0; u < numNodes; ++u) {
        for (const auto& neighbor : edges[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;
            allEdges.push_back(Edge(u, v, weight));
        }
    }

    // Sort edges by weight
    std::sort(allEdges.begin(), allEdges.end(), compareEdges);

    std::vector<int> parent(numNodes);
    std::vector<int> rank(numNodes, 0);
    for (int i = 0; i < numNodes; ++i)
        parent[i] = i;

    for (const Edge& edge : allEdges) {
        int u = edge.u;
        int v = edge.v;
        int weight = edge.weight;

        // Check if adding this edge forms a cycle
        if (find(u, parent) != find(v, parent)) {
            minSpanTree[u][v] = weight;
            minSpanTree[v][u] = weight;
            merge(u, v, parent, rank);
        }
    }
}

//  g++ kruskal.cpp -o main -std=c++11  
int main(int argc, char **argv) {
    int numNodes = edges.size();
    Matrix minSpanTree(numNodes, std::vector<int>(numNodes, 0));

    kruskal(edges, minSpanTree);

    // Output the minimum spanning tree
    std::cout << "Minimum Spanning Tree:" << std::endl;
    for (int i = 0; i < numNodes; ++i) {
        for (int j = 0; j < numNodes; ++j) {
            std::cout << minSpanTree[i][j] << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}